وبلاگ سهراب جلوه گر جلوه‌گر؛ هوش مصنوعی

██ متن فصل هیجدهم نسخه‌ی رایگان ایبوک هوش مصنوعی ██

 

مترجم: سهراب جلوه گر جلوه‌گر

 

فصل الگوریتم‌های ژنتیکی

 

توجّه:      

برای یادگیری بهتر مطلب‌های این فصل بهتر است قسمت «الگوریتم‌های ژنتیکی» موجود در فصل «الگوریتم‌های جستجوی محلّی» همین کتاب الکترونیکی را هم بخوانید.

فهرست برخی از عنوان‌های نوشته‌ها

تاریخچه

تعریف الگوریتم‌های ژنتیکی

تکامل‌ در دنیای واقعی

الگوریتم‌های ژنتیکی

گوناگونی‌های زیاد الگوریتم‌های ژنتیکی

کاربردهای الگوریتم‌های ژنتیکی

 

تئوری تکاملی داروین(باقی ماندن شایسته‌ترین  یا مناسب‌ترین)

 

هِربِرت سپِنسِر

        این تئوری به وسیله‌ی هِرْبِرْتْ سْپِنْسِرْ  و چارْلْزْ رابِرْتْ دارْوینْ  به وجود آمد. این تئوری می‌گوید‌: گونه‌هایی باقی می‌مانند که می‌توانند بر مشکلات‌ غلبه کنند.      

چارلز داروین

 

شکل بالا- این شکل بیان کننده‌ی نظریّه‌ی تکامل در انسان است.

تاریخچه

 

جان هِنری هالِند  الگوریتم‌های ژنتیکی در دهه‌ی هفتاد میلادی‌ به وسیله‌ی جانْ هِنْری هالِنْدْ ‌ بیان شد‌؛ در دهه‌ی هشتاد میلادی‌ عمومیّت یافت و براساس تئوری تکاملی داروین(باقی ماندن شایسته‌ترین یا مناسب‌ترین) بود‌. الگوریتم‌های ژنتیکی‌ می‌توانند برای حلّ انواعی از مسأله‌ها که با استفاده از روش‌های دیگر‌، برای حل‌، آسان نمی‌باشند، مورد استفاده قرار گیرند‌.

تعریف الگوریتم‌های ژنتیکی

 تعریف اوّل- یک الگوریتم جستجو که رشته‌های دودویی بهینه را با پردازش یک جمعیّت اولیّه‌ی تصادفی از رشته‌ها‌، با استفاده از جهش مصنوعی، عمل تعویض  و عملگرهای انتخاب تولید می‌کند. (گُلْدْبِرْگْ ، 1989 ميلادي).

 تعریف دوّم- یک الگوریتم تکاملی‌ که هر فرد(راه حل) را با استفاده از برخی فرم‌های رمزشده‌، که کُرُوموزوم  یا ژِنوم، نامیده می‌شوند‌، به وجود می‌آورد.

تکامل‌ در دنیای واقعی

هر سلّول  یک موجود زنده‌ دارای یک هسته  است؛ و در هسته،  کروموزوم‌هایی وجود دارد‌؛ هر کروموزوم‌، شامل یک مجموعه از ژِنْ ‌ها می‌باشد‌؛ هر ژن‌ برخی از ویژگی‌های(خواصّ) موجود زنده (مانند رنگ چشم) را تعیین می‌کند‌. یک مجموعه از ژن‌ها‌ در برخی از موردها‌ ژِنوتیپ(ژِنوتایپ) ‌ نامیده می‌شود‌. یک مجموعه از ویژگی‌ها (نظیر رنگ چشم)، گاهی فِنوتیپ(فِنوتایپ)  نامیده می‌شود‌. انتشار(زاد و ولد)‌، شامل جفت‌گیری  ژن‌هاي والدین و سپس‌ مقدار کوچکی‌ جهش ‌ می‌باشد‌. تکامل‌ براساس «بقای مناسب‌ترین یا شایسته‌ترین» می‌باشد‌.

 

شکل بالا- سلّول، هسته، کروموزوم و ژن

 

شکل بالا- کروموزوم واقعی در زیر میکروسکوپ

 

الگوریتم‌های ژنتیکی

شروع‌ با یک تصوّر

فرض کنید که شما مشکلی دارید و نمی‌دانید که چگونه آن را حل نمایید‌. برای حلّ این مشکل‌ چه کار می‌توانید بکنید‌؟، آیا می‌توانید به طریقی‌ از یک کامپیوتر‌ برای پیدا کردن یک راه حل‌ استفاده نمایید‌؟؛ این کار‌ باید خوب باشد‌! می‌توانید آن را انجام دهید‌؟.

یک راه حلّ گنگ

 یک الگوریتم «تولید و تست گنگ»‌:

تکرار کن

        یک راه حلّ ممکن تصادفی را تولید کن

        راه حل‌ را امتحان کن و خوب بودن آن را بسنج

تا موقعی که راه حل‌ به اندازه‌ی کافی‌ خوب باشد

پایان الگوریتم

آیا ما می‌توانیم از این ایده‌ی گنگ‌ استفاده نماییم‌؟

برخی وقت‌ها‌ بله‌: در صورتی که تعداد راه حل‌های اندکی وجود داشته باشد و شما به اندازه‌ی کافی‌ زمان در اختیار داشته باشید‌، آنگاه‌ روش‌های این فُرمی‌ می‌توانند استفاده شوند‌. امّا برای بیش‌ترِ مسأله‌ها‌ نمی‌توانیم از این راه حل‌ها استفاده نماییم‌: در زمانی که راه حل‌های ممکن‌، زیاد باشند و شما به اندازه‌ی کافی‌ زمان برای امتحان همه‌ی آنها نداشته باشید‌، این راه حل‌ها نمی‌توانند استفاده شوند‌.

ایده‌ای که کم‌تر دارای گنگ بودن می‌باشد (الگوریتم ژنتیکی)

  الگوریتم

یک مجموعه‌ی تصادفی از راه حل‌ها را تولید نمایید

تکرارکن

        هر راه حلّ موجود در مجموعه را امتحان کن و آنها را رُتبه‌بندی کن

        برخی از راه حل‌های بد را از مجموعه بَردار

        برخی از راه حل‌های خوب را تکثیر(زیاد) کن

                برخی از تغییرات کوچک را در مورد آنها به کار بِبَر

تا زمانی که بهترین راه حل‌ به اندازه‌ی کافی‌ خوب شود

پایان الگوریتم

چگونه شما یک راه حل را کد می‌کنید‌؟

 بدیهی است که این‌، وابسته به مسأله می‌باشد‌! الگوریتم‌های ژنتیکی‌ اغلب،‌ راه حل‌ها را به صورت رشته‌های بیتیِ  باطول ثابت(ژنوتیپ یا کروموزوم)‌ کد می‌کنند (به عنوان مثال‌، 101110‌، 111111‌، 000101)‌؛ هر بیت(ژن)‌، برخی از ویژگی‌های راه حل‌های ارائه شده برای مسأله را بیان می‌کند‌. برای اینکه الگوریتم‌های ژنتیکی‌ کار کنند‌، نیاز به این داریم که هر رشته را تست نماییم و به آن‌ امتیازی بدهیم که نشان دهنده‌ی چگونگی خوب بودن آن باشد‌.

 مثال – حَفر برای نفت

 

شکل بالا- تصویری از یک چاه نفت

تصوّر کنید که شما باید برای نفت‌، جایی را در طول یک جادّه‌ی بیابانی یک کیلومتری‌ حفر نمایید‌.

مسأله‌: بهترین مکان در جادّه را که بیش‌ترین مقدار نفت را در روز‌ تولید می‌کند‌، انتخاب نمایید.

می‌توانیم هر راه حل را به صورت یک وضعیّت در جادّه نمایش دهیم‌. تصوّر نمایید که تمام اعداد‌، بین [1000، 0‌]‌ باشند‌.

کجا را برای نفت‌ حفر نماییم‌؟ 

 

مجموعه‌ی همه‌ی راه حل‌های ممکن [1000،0]‌، فضای جستجو یا فضای حالت‌ نام دارد‌. در این مورد‌ این فقط یک عدد است؛ امّا می‌تواند تعداد زیادی عدد یا سمبل باشد‌. همان طور که گفتیم، اغلب‌، الگوریتم‌های ژنتیکی، اعداد را به صورت دودویی(باینری)‌ کد می‌کنند‌. در مورد این مثال‌، ده بیت را، که برای نمایش 0‌ ... 1000‌ کافی است، انتخاب می‌نماییم‌.

تبدیل به رشته‌ی باینری

1      2      4      8      16    32    64    128   256   512  

0      0      1      0      0      0      0      1      1      1      900

0      0      1      1      0      1      0      0      1      0      300

1      1      1      1      1      1      1      1      1      1      1023

 تعریف- در الگوریتم‌های ژنتیکی، این رشته‌های کد شده‌‌ گاهی ژنوتیپ یا کروموزوم نامیده می‌شوند و بیت‌های تکی‌ گاهی وقت‌ها‌ ژن‌ نامیده می‌شوند‌.

 

خلاصه

تا‌کنون دیدیم که چگونه راه حل‌ها را به صورت یک عدد‌ بیان نماییم‌؛ یک عدد را به صورت یک رشته‌ی بیتی‌ کد کردیم‌. یک رتبه یا درجه را برای هر عدد داده شده‌، به منظور تعیین میزان خوب بودن آن راه‌، به آن عدد‌ نسبت می‌دهیم که اغلب‌ تابع شایستگی ‌ نامیده می‌شود‌؛ در شکل قبلی، این اعداد برای دو راه حلّ 1 و 2، به رنگ قرمز نشان داده شده‌اند(عددهای 30 و 5). مثال نفت‌ در واقع‌ بهینه‌سازی با استفاده از یک تابع f(x) است، که ما باید پارامتر x را تطبیق دهیم‌.

فضای جستجو

برای یک تابع ساده‌ی f(x)‌، فضای جستجو یک بعدی است‌، امّا با کد کردن چند مقدار به کروموزوم‌، ابعاد زیادی می‌تواند به وجود آید‌؛ به عنوان مثال‌، برای حالت دو بعدی‌، تابع f‌، به صورت f(x,y) خواهد بود‌‌. فضای جستجو‌ می‌تواند به صورت یک سطح باشد‌، که در آن، هر چه شایستگی بیش‌تر باشد، ارتفاع نقطه بیش‌تر است. هر ژنوتایپ(کروموزوم یا راه حلّ) ممکن‌، یک نقطه در فضا است. یک الگوریتم ژنتیکی‌ تلاش می‌کند که نقطه‌ها را به جاهای بهتر(‌با شایستگی بالاتر‌)، در فضا، منتقل نماید‌. در زیر‌، سه نمونه از منظره‌های شایستگی را مشاهده می‌نماییم‌:

         

         

بدیهی است که نوع فضای جستجو تعیین می‌کند که چگونه یک الگوریتم ژنتیکی‌ کار کند‌. یک فضای کاملاً تصادفی‌ برای یک الگوریتم ژنتیکی‌، بد خواهد بود‌؛ همچنین‌ الگوریتم‌های ژنتیکی‌ اگر فضاهای جستجو شامل تعداد زیادی از موردهای تصادفی باشند‌، ممکن است در ماکزیمم محلّی بیفتند‌.

اضافه کردن جنسیّت‌- عمل تعویض

گرچه الگوریتمی که ما گفتیم‌ برای فضاهای جستجوی ساده‌، کار می‌کند‌، امّا این الگوریتم‌ هنوز خیلی ساده است‌. این الگوریتم‌ به جهش‌های تصادفی‌ برای یافتن یک راه حلّ خوب‌، وابسته می‌باشد‌.

 مطلب مهم:      

با اضافه نمودن جنسیّت به این الگوریتم‌ می‌توانیم نتایج بهتری را به دست آوریم‌؛ این کار‌ با انتخاب دو والد‌، در موقع تکثیر  و ترکیب ژن‌های آنها برای تولید فرزند‌، انجام می‌شود‌؛ به بیان دیگر، دو رشته‌ی بیتی(‌کروموزوم‌) والد با امتیاز بالا انتخاب می‌شوند و با استفاده از تعویض‌، با هم‌ ترکیب می‌شوند‌؛ در نتیجه دو فرزند(‌رشته‌ی بیتی‌)‌ به وجود می‌آیند و سپس هر فرزند‌ هم ممکن است به صورت تصادفی‌ تغییر داده شود، که ‌به این کار، جهش‌ گفته می‌شود‌.

انتخاب والدها

روش‌های زیادی برای انتخاب کروموزوم‌های با امتیاز بهتر‌ وجود دارد‌. امتیاز‌، اغلب‌، شایستگی ‌  نامیده می‌شود‌. [برای این کار] از روش «چَرخِشِ رولِت» ‌ می‌توان به صورت زیر‌ استفاده نمود‌:

-       شایستگی همه‌ی کروموزوم‌ها را باهم جمع نمایید‌.

-       یک عدد تصادفی R را، در محدوده‌ی آن(حاصل‌جمع)‌، به وجود آورید‌.

-       اوّلین کروموزوم موجود در جمعیّت را با این شرط که زمانی که همه‌ی شایستگی‌های کروموزوم‌های قبل از آن‌ باهم جمع می‌شوند‌، دست‌کم، مقدار R را بدهد‌، انتخاب نمایید‌.

 

توجّه:      

        قسمت زیر دارای ارتباط بین رنگ‌ها هم هست.

جمعیّت نمونه

شماره       کروموزوم     شایستگی

1      1010011010      1

2      1111100001      2

3      1011001100      3

4      1010000000      1

5      0000010000      3

6      1001011111      5

7      0101010101      1

8      1011100111      2

توجّه کنید که، جمع کلّّ شایستگی‌ها برابر است با: 1+2+3+1+3+5+1+2 = 18

انتخاب والدها با استفاده از روش چرخش رولت(برای جدول قبلی)

 

در شکل بالا توجّه کنید که جمع کلّ شایستگی‌ها برابر است با: 1+2+3+1+3+5+1+2 = 18 و به همین خاطر محدوده از صفر تا 18 در نظر گرفته شده است.

 چرخش رولت، نام یک بازی هم می‌باشد، که در آن، اعدادی به طور نامنظّم روی یک صفحه‌ی دایره‌ای شکل نوشته شده‌اند؛ این صفحه را می‌چرخانند و سپس رهایش می‌کنند تا خودش از حرکت بایستد و عددی را که مقابل نقطه‌ای خاص قرار گرفته را برمی‌گزینند.

 

شکل بالا- صفحه‌ی بازی چرخش رولت

تعویض(‌جفت‌گیری‌)

برای کروموزوم‌های شماره‌ی4(1010000000) و 6(1001011111)، که در قسمت قبل انتخاب کردیم، نقطه‌ی تعویض را به صورت تصادفی برابر با 3 در نظر می‌گیریم؛ داریم:

 

جهش

یک یا بیش‌تر ژن‌(بیت)، به صورت تصادفی‌، به یک مقدار تصادفی‌، جهش داده می‌شوند‌، مثلاً‌:

(بعد از انجام عمل جهش)1101011111 →   1111111111(قبل از انجام عمل جهش)

 در مورد مثال قبلی‌، داریم‌:

 

توجّه:      

        پایان قسمت دارای ارتباط بین رنگ‌ها!

 

برگشت به الگوریتم ژنتیکی [و تکمیل آن]

  الگوریتم

یک جمعیّت را با استفاده از کروموزوم‌های تصادفی‌ تولید کن

برای هر نسل‌ کارهای زیر را انجام بده

        شایستگی هر کروموزوم را محاسبه کن

                کارهای زیر را تکرار کن

                        انتخاب رولت را برای انتخاب جفت‌های والدها به کار ببر

                        فرزند را با استفاده از انجام عمل تعویض و جهش‌ تولید نما

                تا زمانی که جمعیّت جدید‌ تولید شود

تا زمانی که بهترین راه حل به اندازه‌ی کافی‌ خوب شود

پایان الگوریتم

گوناگونی‌های زیاد الگوریتم‌های ژنتیکی

به خاطر موردهای زیر‌ الگوریتم‌های ژنتیکی‌ دارای گوناگونی زیادی هستند‌:

•       انواع مختلف انتخاب که [با استفاده از روش چرخش] رولت نیستند‌؛ مثل‌ روش‌های مسابقه‌ای ‌، گزینش بهترین‌ها(نخبه‌سالاری)  و غیره‌.

•       تفاوت در جفت‌گیری(تعویض)‌؛ مثل‌ روش تعویض چند نقطه‌ای‌.

•       انواع مختلف کد کردن رشته‌ی بیتی‌

•       انواع مختلف جهش

تعویض‌ چگونه کار می‌کند‌؟

تعداد زیادی نظریّه در این مورد‌ وجود دارد‌، البتّه‌ برخی مخالفت‌ها هم با این نظریّه‌ها وجود دارد‌؛ هالِند‌ نظریّه‌ی «‌الگو» را معرّفی کرد‌؛ این ایده می‌گوید که، تعویض‌، بیت‌های خوب والدین مختلف را نگهداری می‌کند و آنها را برای تولید راه حل‌های بهتر‌ ترکیب می‌نماید‌؛ بنابراین‌ یک الگوی خوب کد کننده‌ باید بیت‌های خوب را در طول تعویض و جهش‌ نگهداری نماید‌.

کاربردهای الگوریتم‌های ژنتیکی

الگوریتم‌های ژنتیکی‌ در بسیاری از موردها و زمینه‌های پژوهشی‌، نظیر مسأله‌های عددی‌؛ مسأله‌ی مسافرت شخص دوره گرد ‌؛ مدار(دُوْر) هَمیلتُونی ‌؛ پیدا کردن شکل مولکول‌های پروتئین‌؛ مسأله‌های NP-سخت‌؛ طرّاحی شبکه‌های عصبی‌؛ توابع، برای به وجود آوردن تصاویر‌؛ مدلسازی شناختی؛ و تئوری بازی‌ها‌ به کار می‌روند‌.

برنامه‌نویسی ژنتیکی

 تعریف- شاخه‌ای از الگوریتم‌های ژنتیکی و یادگیری ماشینی  می‌باشد و یک روش برنامه‌نویسی است که الگوریتم ژنتیکی را برای تمام برنامه‌های کامپیوتری گسترش می‌دهد.  برنامه‌نویسی ژنتیکی‌ به وسیله‌ی گروه دکتر، جان کُوزا ‌ به وجود آمد‌.

 

شکل بالا- دکتر، جان کوزا

 

 

 

چکیده‌ی مطلب‌های فصل هیجدهم

یک الگوریتم ژنتیکی، یک الگوریتم جستجو است که، رشته‌های دودویی بهینه را با پردازش یک جمعیّت اولیّه‌ی تصادفی از رشته‌ها‌، با استفاده از جهش مصنوعی، عمل تعویض و عملگرهای انتخاب تولید می‌کند.

الگوریتم‌های ژنتیکی‌، اغلب‌، راه حل‌ها را به صورت رشته‌های بیتی باطول ثابت(ژنوتیپ یا کروموزوم)‌ کد می‌کنند؛ هر بیت(ژن)‌، برخی از ویژگی‌های راه حل‌های ارائه شده برای مسأله را ارائه می‌کند‌. برای اینکه الگوریتم‌های ژنتیکی‌ کار کنند‌، نیاز به این داریم که هر رشته را تست نماییم و به آن‌ امتیازی بدهیم که نشان دهنده‌ی چگونگی خوب بودن آن باشد‌.

در الگوریتم‌های ژنتیکی، جفت‌گیری(recombination)، همان تعویض(crossover) می‌باشد.

تعویض‌، با انتخاب دو والد(رشته‌ی بیتی یا ‌کروموزوم‌) با امتیاز بالا‌، در موقع تکثیر، و ترکیب ژن‌های آنها، برای تولید دو فرزند(‌رشته‌ی بیتی‌)‌، انجام می‌شود. سپس هر فرزند‌ هم ممکن است به صورت تصادفی‌ تغییر داده شود، که ‌به این کار، جهش‌ گفته می‌شود‌.

یکی از روش‌های انتخاب کروموزوم‌های با امتیاز بهتر، روش چرخش رولت است.